A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Example 1:
Input: m = 3, n = 7 Output: 28
Example 2:
Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down
Example 3:
Input: m = 7, n = 3 Output: 28
Example 4:
Input: m = 3, n = 3 Output: 6
Constraints:
1 <= m, n <= 100- It's guaranteed that the answer will be less than or equal to
2 * 109.
Average Rating: 4.74 (38 votes)
Solution
Overview
Since robot can move either down or right, there is only one path to reach the cells in the first row: right->right->...->right.
The same is valid for the first column, though the path here is down->down-> ...->down.
What about the "inner" cells (m, n)? To such cell one could move
either from the upper cell (m, n - 1), or from the cell on the right
(m - 1, n). That means that the total number of paths to move into (m, n) cell
is uniquePaths(m - 1, n) + uniquePaths(m, n - 1).
Now, one could transform these ideas into 3-liner recursive solution:
This solution is not fast enough to pass all the testcases, though it
could be used as a starting point for the DP solution.
Approach 1: Dynamic Programming
One could rewrite recursive approach into dynamic programming one.
Algorithm
-
Initiate 2D array
d[m][n] = number of paths. To start, put number of paths equal to 1 for the first row and the first column. For the simplicity, one could initiate the whole 2D array by ones. -
Iterate over all "inner" cells:
d[col][row] = d[col - 1][row] + d[col][row - 1]. -
Return
d[m - 1][n - 1].
Implementation
Complexity Analysis
-
Time complexity: O(N×M).
-
Space complexity: O(N×M).
Approach 2: Math (Python3 only)
Could one do better than O(N×M)? The answer is yes.
The problem is a classical combinatorial problem: there are h+v moves to do from start to finish, h=m−1 horizontal moves, and v=n−1 vertical ones. One could choose when to move to the right, i.e. to define h horizontal moves, and that will fix vertical ones. Or, one could choose when to move down, i.e. to define v vertical moves, and that will fix horizontal ones.
In other words, we're asked to compute in how many ways one could choose p elements from p+k elements. In mathematics, that's called binomial coefficients
Ch+vh=Ch+vv=h!v!(h+v)!
The number of horizontal moves to do is h=m−1, the number of vertical moves is v=n−1. That results in a simple formula
Ch+vh=(m−1)!(n−1)!(m+n−2)!
The job is done. Now time complexity will depend on the algorithm to compute factorial function (m+n−2)!. In short, standard computation for k! using the definition requires O(k2logk) time, and that will be not as good as DP algorithm.
The best known algorithm to compute factorial function is done by Peter Borwein. The idea is to express the factorial as a product of prime powers, so that k! can be computed in O(k(logkloglogk)2) time. That's better than O(k2) and hence beats DP algorithm.
The authors prefer not to discuss here various factorial function implementations, and hence provide Python3 solution only, with built-in divide and conquer factorial algorithm. If you're interested in factorial algorithms, please check out good review on this page.
Implementation
Complexity Analysis
-
Time complexity: O((M+N)(log(M+N)loglog(M+N))2).
-
Space complexity: O(1).
May 24, 2020 6:10 PM
3rd solution time complexity is something evil
In the second solution (DP) we only need one row to keep, and we can keep reading from and updating it. That would result in O(n) space instead of O(m*n);
May 29, 2020 12:04 AM
In Python 3.8, there's a new function that calculates n-choose-k directly:
def uniquePaths(self, m: int, n: int) -> int:
return math.comb(m + n - 2, n - 1)
March 28, 2020 4:28 AM
A bit confused by the code for DP implementation. When you create DP table, you use 'n' as the columns. But in the for loop, to iterate over 'col' you use range(1, m). I understand the output is not affected, but the code causes confusion in understanding
March 2, 2020 5:39 PM
Here is an easy Java Version.
// Runtime: O(M*N) Memory: O(N)
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
Last Edit: August 23, 2020 7:15 PM
DP solution doesn't have to hold the whole 2D array.
Only one line needed, so the memory usage becomes O(min(M, N))
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m > n:
m, n = n, m
r = [1] * m
for _ in range(1, n):
for i in range(1, m):
r[i] += r[i - 1]
return r[-1]
Can we not do this in linear time O(m+n) as shown below? I am confused by the statement that, "The best known algorithm to compute factorial function is done by Peter Borwein [and is some crazy complexity]". Honestly I did not read the paper, I was hoping someone could have a layman explanation such as, "because the number of digits grows quickly, multiplication can no longer be thought of as a constant operation".
class Solution {
public int uniquePaths(int m, int n) {
double num = 1;
double denom = 1;
for(int i = 2; i < Math.min(m,n); i++){
denom*=i;
}
for(int i = Math.max(m,n); i <= m+n-2; i++){
num*=i;
}
return (int) (num/(denom));
}
}
Last Edit: June 30, 2020 1:26 PM
The recursion method is quite intuitive, it only needs memorization to pass the tests.
public int uniquePaths(int m, int n) {
int[][] memo = new int[m][n];
return uniquePaths(memo, m - 1, n - 1);
}
private int uniquePaths(int[][] memo, int r, int c) {
if (r == 0 || c == 0) return memo[r][c] = 1;
if (memo[r][c] != 0) return memo[r][c];
return memo[r][c] = uniquePaths(memo, r - 1, c) + uniquePaths(memo, r, c - 1);
}
The simplest math solution in Java needs BigInteger.
import java.math.BigInteger;
class Solution {
public int uniquePaths(int m, int n) {
if (m == 1 || n == 1) return 1;
return factorial(m + n - 2).divide(factorial(m - 1)).divide(factorial(n - 1)).intValue();
}
public BigInteger factorial(int n) {
BigInteger result = BigInteger.ONE;
for (int i = 2; i <= n; i++)
result = result.multiply(BigInteger.valueOf(i));
return result;
}
}
are we really expected to come up with the apporach 3 solution in a real interview?
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 03/27/2021 08:02 | Accepted | 0 ms | 5.9 MB | cpp |
| 06/30/2020 07:41 | Accepted | 0 ms | 6.1 MB | cpp |
| 05/18/2020 16:22 | Accepted | 0 ms | 6 MB | cpp |
| 05/18/2020 16:21 | Wrong Answer | N/A | N/A | cpp |
| 05/18/2020 16:20 | Runtime Error | N/A | N/A | cpp |
xxxxxxxxxxclass Solution {public: int uniquePaths(int m, int n) { int dp[m][n]; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { if(i==0 || j==0) dp[i][j] = 1; } } for(int i=1;i<m;i++) { for(int j=1;j<n;j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; }};


